package leetcode;

import java.util.*;

public class LeetcodeMain87 {
    public String convert(String s, int numRows) {
        if (numRows<2){
            return s;
        }
        List<StringBuilder> list=new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuilder());
        }
        int i=0;
        int flag=-1;
        for (char ch:s.toCharArray()) {
            list.get(i).append(ch);
            if(i==0||i==numRows-1){
                flag=-flag;
            }
            i+=flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : list) res.append(row);
        return res.toString();

    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
    }
    public int count=1;
    public int diameterOfBinaryTree(TreeNode root) {

        depth(root);
        return count-1;
    }
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=depth(root.left);
        int right=depth(root.right);
        count=Math.max(count,left+right+1);
        return Math.max(left,right)+1;
    }
    public int findUnsortedSubarray(int[] nums) {
        if (isSorted(nums)){
            return 0;
        }
        int length=nums.length;
        int[] arr=new int[length];
        System.arraycopy(nums, 0, arr, 0, nums.length);
        Arrays.sort(arr);
        int left=0;
        while (nums[left]==arr[left]){
            left++;
        }
        int right=length-1;
        while (nums[right]==arr[right]){
            right--;
        }
        return right-left+1;
    }
    public boolean isSorted(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]<nums[i-1]){
                return false;
            }
        }
        return true;
    }
    public static void main3(String[] args) {
        LeetcodeMain87 main87=new LeetcodeMain87();
        int[] nums={1,2,3,4};
        main87.findUnsortedSubarray(nums);
        System.out.println();
    }
    public int hammingDistance(int x, int y) {
        int sum=x^y;
        int count=0;
        while (sum!=0){
            sum=sum&(sum-1);
            count++;
        }
        return count;
    }
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list=new ArrayList<>();
        int n=nums.length;
        Set<Integer> set=new HashSet<>();
        for (int num:nums) {
            set.add(num);
        }
        for (int i = 1; i <= n; i++) {
            if (!set.contains(i)){
                list.add(i);
            }
        }
        return list;
    }
    public static void main2(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            String str=in.nextLine();
            int length=str.length();
            StringBuffer buffer=new StringBuffer();
            for (int i = 0; i < length; i++) {
                char ch=str.charAt(i);
                if (Character.isAlphabetic(ch)){
                    buffer.append(ch);
                }else {
                    buffer.append(' ');
                }
            }
            String[] arr=buffer.toString().split(" ");
            for (int i = arr.length-1; i >0 ; i--) {
                System.out.printf("%s ",arr[i]);
            }
            System.out.println(arr[0]);
        }
    }
    public static void main1(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            String str=in.nextLine();
            StringBuffer buffer=new StringBuffer();
            int count=0;
            int length=str.length();
            for (int i = 0; i < length; i++) {
                char ch=str.charAt(i);
                if (ch=='_'){
                    count++;
                }
                else {
                    if (count==1){
                        buffer.append(Character.toUpperCase(ch));
                        count=0;
                    }else {
                        buffer.append(ch);
                    }
                }
            }
            System.out.println(buffer.toString());
        }
    }
}
